Ring buffers are powerful mechanisms for communicating data. A writer writes data to the ring buffer and a reader reads data from the ring buffer. A writer initially writes data at the beginning of the buffer. When the writer fills the buffer, the writer begins writing to the buffer again at the beginning. The writer feeds data to the reader by writing at a point in the buffer that is ahead from the point where the reader is reading from the buffer.
One important feature of a ring buffer is that data is read from the buffer in the same order it is written. Thus, ring buffers are very useful for communicating data associated with an order in that order. This feature is particularly useful for real-time applications, such as processing and communicating of digital audio/video data (“audio/video data”).
A ring buffer is used to communicate audio/video from a provider of audio/video data to a user of audio/video data. An example of such a provider and a user are an audio/video preparation thread and audio/video IO thread on a computer system or electronic device. The audio/video preparation thread is the writer and the audio/video IO thread is the reader. The audio/video preparation thread prepares audio/video data from an audio file, decoding, decompressing, and formatting the data. The prepared audio is ordered according to time. The audio/video data is written to a ring buffer in the time order, where it is read by the audio/video thread in the time order. The audio/video IO thread may be, for example, a thread executing the device driver of an audio or video card. The audio IO thread receives the prepared audio/video data and transmits the data to the card to be played.
In some contexts in which a ring buffer is used, it is important to avoid delaying the reading of a ring buffer by the reader. For example, if the reader is an audio/video IO thread, delaying or impairing the execution of the audio/video IO thread can impact playback quality. To avoid such delay, a reader is assigned a higher execution priority relative to other threads, including a thread executing as a writer. Assigning a higher execution priority gives the thread a greater proportion of CPU time and processing.
Unfortunately, assigning a higher execution priority to a reader is not a panacea. Delays to the reader may nevertheless occur for a variety of reasons. For example, one form of delay stems from the fact that a reader and writer coordinate access to a ring buffer using a locking mechanism. A locking mechanism governs access to a resource and data structures using another set of data structures, such as semaphores, mutexes, or latches. Using a locking mechanism to access a ring buffer inherently entails a layer of overhead. Further, locking contention can cause the writer and reader to block and delay each other.
Specifically, when a writer writes to the ring buffer, it acquires an exclusive lock from the locking mechanism, preventing the reader from accessing the ring buffer. Thus, even when the writer's execution is pre-empted to execute the higher priority reader, the reader is nevertheless blocked by the writer's exclusive lock. In effect, the reader is subordinated to a lower execution priority than that of the writer. Furthermore, because the reader has a higher execution priority, it is being allocated more execution time. Consequently, execution time is shifted away from threads with lower execution priority to a reader that is simply waiting around to become unblocked.
Also, assigning a higher execution priority to the reader increases the likelihood that the reader catches up to the writer. When using a ring buffer, the reader is not allowed to read ahead of the writer and must wait for the writer to “get ahead”. Thus, the reader is delayed when it catches up to the writer and must wait until the writer gets ahead.
Based on the foregoing, there is a clear need for ways to avoid delay of ring buffer readers, particularly those that are given higher execution priority.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.